package chapter4;

/**
 * 分治策略-最大子数组
 */
public class MaxSubArray {

    public static int[] findMaxCrossingSubArray(int[] A, int low, int mid, int high) {
        int maxLeft = 0;
        int maxRight = 0;

        int leftSum = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = mid; i >= low; i--) {
            sum += A[i];
            if (sum > leftSum) {
                leftSum = sum;
                maxLeft = i;
            }
        }
        int rightSum = Integer.MIN_VALUE;
        sum = 0;
        for (int j = mid + 1; j <= high; j++) {
            sum += A[j];
            if (sum > rightSum) {
                rightSum = sum;
                maxRight = j;
            }
        }

        return new int[]{maxLeft, maxRight, leftSum + rightSum};
    }

    public static int[] findMaxSubArray(int[] A, int low, int high) {
        // base case
        if (low == high) {
            return new int[]{low, high, A[low]};
        } else if (high - low <= crossPoint()) {
            return findMaxSubArray2(A);
        } else {
            // 分治法先找到一个折中位置
            int mid = (low + high) / 2;
            // 最大子数组可能存在于 low - mid 之中
            int[] left = findMaxSubArray(A, low, mid);
            // 最大子数组可能存在于 mid+1 - high 之中
            int[] right = findMaxSubArray(A, mid + 1, high);
            // 可能会横跨mid,存在 low ~ mid ~ high 之中
            int[] crow = findMaxCrossingSubArray(A, low, mid, high);
            // 如果左边数组中的和大于右边段及横跨段的和,则返回左边段的值
            if (left[2] >= right[2] && left[2] >= crow[2]) {
                return left;
            } else if (right[2] >= left[2] && left[2] >= right[2]) {
                // 如果右边数组中的和大于左边段及横跨段的和,则返回左边段的值
                return right;
            }
            // 否则返回横跨段的值
            return crow;
        }
    }

    public static int[] findMaxSubArray2(int[] A) {
        int max = Integer.MIN_VALUE;
        int left = 0;
        int right = 0;
        for (int i = 0; i < A.length; i++) {
            int sum = A[i];
            for (int j = i + 1; j < A.length; j++) {
                sum += A[j];
                if (sum > max) {
                    max = sum;
                    left = i;
                    right = j;
                }
            }
        }
        return new int[]{left, right, max};
    }

    public static int crossPoint() {
        for (int i = 1; ; i++) {
            if (i * (Math.log(i) / Math.log(2)) >= i * i) {
                return i;
            }
        }
    }

    public static int[] findMaxSubArray3(int[] A) {
        int left = 0;
        int right = 0;
        int max = Integer.MIN_VALUE;

        int slow = 0;
        int fast = 1;
        int sum = 0;

        while (slow < fast && fast < A.length) {
            for (int i = slow; i <= fast; i++) {
                sum += A[i];
            }
            if (sum >= max) {
                max = sum;
                left = slow;
                right = fast;

                fast++;
            } else {
                slow++;
                fast = slow + 1;
            }
            sum = 0;
        }
        return new int[]{left, right, max};
    }

}
